# -*- coding: utf-8 -*-

"""
@Time    : 2020/2/20 11:47
@Author  : Chen Liu
@FileName: binary_tree.py
@Software: PyCharm

"""


# 如何将二叉树的节点连起来？？？？？？？-----使用深度优先搜索（递归构建左子树和右子树）
# 二叉树的构建和遍历

class tree_node:
    def __init__(self, element=None):
        self.element = element
        self.left = None
        self.right = None


# 解法一：递归建树
def create_tree(data, index=0):
    """深度优先遍历，递归建树"""
    if len(data) == 0:
        return None
    root = None
    if index < len(data):
        root = tree_node(data[index])
        print("root: ", root.element)
        root.left = create_tree(data, 2*index+1)
        root.right = create_tree(data, 2*index+2)

        # 无法将树节点连到一块
        # if root and 2*i+1 < len(data):
        #     root.left = tree_node(data[2*i+1])
        #     print(root.left.element)
        # if root and 2*i+2 < len(data):
        #     root.right = tree_node(data[2*i+2])
        #     print(root.right.element)

    return root


# 解法二：层次建树--利用队列先进先出的特性
from collections import deque
def add_node(num, root, queue):
    q = queue
    node = tree_node(num)
    if not root:
        root = node
        q.append(root)
    else:
        node = q[0]
        if not node.left:
            node.left = tree_node(num)
            q.append(node.left)
        else:
            node.right = tree_node(num)
            q.append(node.right)
            q.popleft()   # 如果父节点左右节点都添加了节点，就删除父节点

    return root, q


def cengci_tree(data):
    root = None
    q = deque()
    for i in data:
        root, q = add_node(i, root, q)

    return root


def cengci_search(root):
    """宽度优先遍历，层次搜索"""
    if not root:
        return None
    current_node = [root]
    while current_node:
        next_node = []
        for node in current_node:
            print(node.element)
            if node.left:
                next_node.append(node.left)
            if node.right:
                next_node.append(node.right)
        current_node = next_node


if __name__ == "__main__":
    data = [1, 2, 3, 4, 5]
    # root = create_tree(data)

    root = cengci_tree(data)
    cengci_search(root)
